package lc;

public class TrappingRainWater {
    public int trap(int[] A) {
    	if (A.length < 3) {
    		return 0;
    	}
    	
    	int max=0;
    	int [] leftMax = new int [A.length];
    	for (int i=0; i<A.length; i++) {
    		if (A[i] > max) {
    			max = A[i];
    		}
			leftMax[i] = max;
    	}
    	
    	max = 0;
    	int [] rightMax = new int [A.length];
    	for (int i=A.length-1; i>=0; i--) {
    		if (A[i] > max) {
    			max = A[i];
    		}
			rightMax[i] = max;    		
    	}
    	
    	int trap=0;
    	for (int i=0; i<A.length; i++) {
    		int min = Math.min(leftMax[i], rightMax[i]);
			int diff = min - A[i];
			trap += diff;
    	}
    	return trap;
    }

    public static void main(String ...strings) {
    	TrappingRainWater sol = new TrappingRainWater();
    	int [] A = {0,1,0,2,1,0,1,3,2,1,2,1};
    	int trap = sol.trap(A);
    	System.out.println(trap);
    }
}
